#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define int long long

using namespace std;

typedef pair<int,int> pii;
typedef pair<int,pii> pip;
const int N = 1e5 + 10;
int n,k,ans;
int arr[N];
vector<int> S[N];
vector<pip> Q[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

struct{
    #define ls(u) (u << 1)
    #define rs(u) (u << 1 | 1)
    #define val(u) (tr[u].val)
    #define mid (tr[u].l + tr[u].r >> 1)

    struct value{
        int Min,cnt;

        value friend operator +(const value &a,const value &b){
            value res;
            res.Min = min(a.Min,b.Min);
            res.cnt = ((a.Min == res.Min) ? a.cnt : 0) + ((b.Min == res.Min) ? b.cnt : 0);
            return res;
        }
    };

    struct node{
        int l,r,tag;
        value val;
    }tr[N << 2];

    inline void calc(int u,int k){ val(u).Min += k,tr[u].tag += k; }
    inline void pushup(int u){ val(u) = val(ls(u)) + val(rs(u)); }

    inline void pushdown(int u){
        if (tr[u].tag){ calc(ls(u),tr[u].tag); calc(rs(u),tr[u].tag); }
        tr[u].tag = 0;
    }

    inline void build(int u,int l,int r){
        tr[u] = {l,r,0,{0,0}};
        if (l == r) return (val(u) = {0,1}),void();
        build(ls(u),l,mid); build(rs(u),mid + 1,r);
        pushup(u);
    }

    inline void modify(int u,int l,int r,int k){
        if (l <= tr[u].l && tr[u].r <= r) return calc(u,k);
        pushdown(u);
        if (l <= mid) modify(ls(u),l,r,k);
        if (r > mid) modify(rs(u),l,r,k);
        pushup(u);
    }

    #undef ls
    #undef rs
    #undef val
    #undef mid
}T;

inline int calc(int st){
    int sum = 0; T.build(1,1,n);
    for (re int i = 1;i <= n;i++) Q[i].clear();
    for (re int l = 1;l <= k;l++){
        if (!((st >> (l - 1)) & 1)) continue;
        for (re int i = 1;i <= n;i++){
            for (re int j = l;j < S[i].size() - 1;j++){
                Q[S[i][j - l] + 1].push_back({1,{S[i][j],S[i][j + 1] - 1}});
                Q[S[i][j - l + 1] + 1].push_back({-1,{S[i][j],S[i][j + 1] - 1}});
            }
        }
    }
    for (re int i = 1;i <= n;i++){
        for (pip p:Q[i]) T.modify(1,p.snd.fst,p.snd.snd,p.fst);
        if (T.tr[1].val.Min) sum += n;
        else sum += (n - T.tr[1].val.cnt);
    } return sum;
}

signed main(){
    freopen("reporter.in","r",stdin);
    freopen("reporter.out","w",stdout);
    n = read(),k = read();
    for (re int i = 1;i <= n;i++) S[i].push_back(0);
    for (re int i = 1;i <= n;i++) S[arr[i] = read()].push_back(i);
    for (re int i = 1;i <= n;i++) S[i].push_back(n + 1);
    for (re int st = 1;st < (1 << k);st++){
        int res = calc(st);
        // cerr << st << " " << res << " ???\n";
        if (__builtin_popcount(st) & 1) ans += res;
        else ans -= res;
    } printf("%lld",ans);
    return 0;
}